package g

import (
	"fmt"
	"sort"
)

/*
 * @lc app=leetcode.cn id=15 lang=golang
 *
 * [15] 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

0 <= nums.length <= 3000
-105 <= nums[i] <= 105
*/

// @lc code=start
func threeSum(nums []int) [][]int {
	return threeSumSort(nums)
}

// threeSumSort 先排序，三层循环，充分利用规则检索实现o(n^2)复杂度
func threeSumSort(nums []int) [][]int {
	sort.Ints(nums)
	var result [][]int
	for i := 0; i < len(nums); i++ {
		// 重复元素跳过，因为nums[i-1]已经匹配完，所以nums[i]即使匹配也是重复的，题目要求不能重复
		if i > 0 && nums[i] == nums[i-1] { // !!! 这里应该不对，题目要求是 下标不相等，而不是值不相等
			continue
		}
		k := len(nums) - 1
		for j := i + 1; j < len(nums); j++ {
			if j > i+1 && nums[j] == nums[j-1] { // 重复元素跳过
				continue
			}
			for ; k > j; k-- {
				if nums[i]+nums[j]+nums[k] <= 0 {
					break
				}
			}
			if j == k { // 不允许重复
				break
			}
			if nums[j]+nums[k]+nums[i] == 0 {
				result = append(result, []int{nums[i], nums[j], nums[k]})
			}
		}
	}
	return result
}

// threeSumMap 两两组合，然后再组合
func threeSumMap(nums []int) [][]int {
	nums = rmDupSrc(nums) // 为了减少循环次数，没有也行
	// 两两组合
	twoSums := make(map[int][]int)
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if _, ok := twoSums[nums[i]+nums[j]]; ok {
				twoSums[nums[i]+nums[j]] = append(twoSums[nums[i]+nums[j]], i, j)
				continue
			}
			twoSums[nums[i]+nums[j]] = []int{i, j}
		}
	}

	// 配对
	var result [][]int
	for i := 0; i < len(nums); i++ {
		if vals, ok := twoSums[0-nums[i]]; ok {
			vals = rmDup(vals, nums) // 为了减少循环次数，没有也行
			for j := 0; j < len(vals); j += 2 {
				if i != vals[j] && i != vals[j+1] {
					val := []int{nums[i], nums[vals[j]], nums[vals[j+1]]}
					sort.Slice(val, func(i, j int) bool {
						return val[i] < val[j]
					})
					result = append(result, val)
				}
			}
		}
	}

	return rmDupSort(result)
}

// rmDupSrc 去重，重复数字最多流3个
func rmDupSrc(nums []int) []int {
	var newNums []int
	numsRmDup := make(map[int][]int)
	for i := 0; i < len(nums); i++ {
		if _, ok := numsRmDup[nums[i]]; ok {
			if len(numsRmDup[nums[i]]) < 3 {
				numsRmDup[nums[i]] = append(numsRmDup[nums[i]], nums[i])
				newNums = append(newNums, nums[i])
			}
			continue
		}
		numsRmDup[nums[i]] = []int{nums[i]}
		newNums = append(newNums, nums[i])
	}
	return newNums
}

// rmDup 去重
func rmDup(indexs []int, nums []int) []int {
	values := make(map[string]bool)
	var resultRmDup []int
	for i := 0; i < len(indexs); i += 2 {
		key := fmt.Sprintf("%v%v", nums[indexs[i]], nums[indexs[i+1]])
		if !values[key] {
			resultRmDup = append(resultRmDup, indexs[i], indexs[i+1])
			values[key] = true
		}
	}
	return resultRmDup
}

// rmDupSort 去重
func rmDupSort(result [][]int) [][]int {
	values := make(map[string]bool)
	var resultRmDup [][]int
	for _, val := range result {
		key := fmt.Sprintf("%v%v%v", val[0], val[1], val[2])
		if !values[key] {
			resultRmDup = append(resultRmDup, val)
			values[key] = true
		}
	}

	// 排序
	sort.Slice(resultRmDup, func(i, j int) bool {
		if resultRmDup[i][0] != resultRmDup[j][0] {
			return resultRmDup[i][0] < resultRmDup[j][0]
		} else if resultRmDup[i][1] != resultRmDup[j][1] {
			return resultRmDup[i][1] < resultRmDup[j][1]
		}
		return resultRmDup[i][2] < resultRmDup[j][2]
	})
	return resultRmDup
}

// @lc code=end
